package arithmetic2;

import utils.PrintUtil;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by AJie on 2019/8/6
 * Function :
 *编写一个程序，找到两个单链表相交的起始节点。
 * 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
 *
 *
 */
public class T_160_TwoLinkedListMeet {
    public static void main(String[] args) {
        ListNode f4 = new ListNode(4);
        ListNode f1 = new ListNode(1);
        f4.next = f1;

        ListNode t5 = new ListNode(5);
        ListNode t0 = new ListNode(0);
        ListNode t1 = new ListNode(1);
        t5.next = t0;
        t0.next=t1;

        ListNode c8 = new ListNode(8);
        ListNode c4 = new ListNode(4);
        ListNode c5 = new ListNode(5);
        c8.next=c4;
        c4.next=c5;

        f1.next=c8;
        t1.next=c8;

        ListNode intersectionNode = getIntersectionNode2(f4, t5);
        PrintUtil.print(intersectionNode);

    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //相遇，或者永不相遇 null
        // 1 暴力法 O n^2
        // O(MAX A B)

        //暴利法
        ListNode tempB= headB;
        while (headA!=null){
            System.out.println(headA.val);
            headB = tempB;
            while (headB!=null){
//                System.out.println("--- "+headB.val);
                if (headA==headB)return headB;
                headB = headB.next;
            }
           headA= headA.next;
        }
        return null;
    }

    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        //相遇，或者永不相遇 null
        // 1 暴力法 O n^2
        // O(MAX A B)
        Set<ListNode> setA = new HashSet<>();
        Set<ListNode> setB = new HashSet<>();
        while (headA!=null ||headB!=null){
            if (headA != null) {
                setA.add(headA);
            }
            if (headB!=null){
                setB.add(headB);
            }
            if (headB!=null && setA.contains(headB)){
                return headB;
            }
            if (headA!=null && setB.contains(headA)){
                return headA;
            }

            if (headA!=null){
                headA = headA.next;
            }
            if (headB!=null){
                headB = headB.next;
            }
        }
        return null;
    }
}
